/** class global
 * @Author Hussein Patwa
 * @Date 10 March 2007
 * This class implements the global trending algorithm, Fig. 6 on KDD paper.
 */

import java.util.*;
import java.lang.Double;

@SuppressWarnings("all")
public class global {

    HashSet paths;
    ArrayList path; // ArrayList to hold spatial objects 

    int minLength; // length above which path is considered established
    int maxLength; // length above which path is assumed
    int min_conf; // min_conf as noted in pseudo code

    class observation { // define what an observation is
	double dist; // distance from X co-ordinate
	double diff; // distance from Y co-ordinate

	observation(double dist, double diff) {
	    this.dist = dist;
	    this.diff = diff;
}
    }

    public global(NeighbourhoodInfo neighbourInfo,ArrayList data,int index,int minLength, int maxLength, double min_conf){
	paths = computeAllPaths(neighbourInfo,index,minLength);
        //System.out.println("Number of Paths: "+paths.size());
        findTrends(index,data);
    }
    
    HashSet computeAllPaths(NeighbourhoodInfo neighbourInfo, int index,int minLength){
        //compute all the paths from the spatial object 
        //specified by the index using the neighbourhood information
        HashSet rtn = new HashSet();
        Vector tempNeighbours = neighbourInfo.getNeighbourhoodAreaIDs(index);
        //System.out.println("index: "+index+" neighbours : "+tempNeighbours);
        for(Iterator i = tempNeighbours.iterator();i.hasNext();){
            Integer node = (Integer)i.next();
            ArrayList tempPath = new ArrayList(new Integer(index));
            tempPath.add(new Integer(node));
            rtn.add(tempPath);
            //System.out.println(tempPath);
        }
        for(int j=0;j<minLength;j++)
                rtn.addAll(extendPath(rtn,neighbourInfo));
        return rtn;
    }
    
    HashSet extendPath(HashSet paths, NeighbourhoodInfo neighbourInfo){
        HashSet rtn = new HashSet();
        for(Iterator k = paths.iterator();k.hasNext();){
            ArrayList path = (ArrayList)k.next();
            int index = ((Integer)path.get(path.size()-1)).intValue();
            Vector tempNeighbours = neighbourInfo.getNeighbourhoodAreaIDs(index);
            //System.out.println("index: "+index+" neighbours : "+tempNeighbours);
            for(Iterator i = tempNeighbours.iterator();i.hasNext();){
                Integer node = (Integer)i.next();
                if(!path.contains(node)){
                    ArrayList tempPath = new ArrayList();
                    tempPath.addAll(path);
                    tempPath.add(node);
                    rtn.add(tempPath);
                    //System.out.println(tempPath);
                }
                // tempPath.remove(note);
                // rtn.remove(tempPath);
            }
        }
        return rtn;
    }
    
    // 
    public void findTrends(int index,ArrayList data){
        for(Iterator i = paths.iterator();i.hasNext();){
            path = (ArrayList)i.next(); // Move first element of paths to path
            TreeMap PathObs = new TreeMap();
            for(int j=0; j<path.size(minLength); j++) // initialise counter that will track through the colums of the set paths
            {
        	//System.out.println(path.size());
                Integer currentIndex = (Integer)path.get(j);
                spatialobject o = (spatialobject)data.get(index);
                spatialobject object = (spatialobject)data.get(currentIndex);
                double dist = Math.sqrt(Math.pow((object.getX()-o.getX()),2)+Math.pow((object.getY()-o.getY()),2)); // calculate the difference in the x co-ordinate
                double diff = object.getV()-o.getV(); // calculate the difference in the y co-ordinate
                //observation obsTemp = new observation(dist,diff); // insert distX into observations
                PathObs.put(dist,diff);// insert distY into observations
                TreeMap predObs = getRegressionPredictions(PathObs);
                //System.out.println(PathObs+"  "+predObs);
                
                TreeMap test = getTreeMapOfObservedAndPredicted(PathObs,predObs);
                paths.remove(0); // Remove the first position to shift everything back a place
            }
    
            // Correlation function
            double corr = getCorrelationCoefficient(test);
        }

        
    }
}

TreeMap getTreeMapOfObservedAndPredicted(TreeMap obs,TreeMap pred){
    TreeMap rtn = new TreeMap();
    for(Iterator i =obs.entrySet().iterator();i.hasNext();){
        Map.Entry e = (Map.Entry)i.next();
        Double key = (Double)e.getKey();
        Double tempObs = (Double)obs.get(key);
        Double tempPred = (Double)pred.get(key);
        rtn.put(tempObs,tempPred);
    }
    return rtn;
}


double getCorrelationCoefficient(TreeMap obsPred){
    double sigmaX = sigmaX(obsPred.keySet());
    double sigmaX2 = sigmaXSquare(obsPred.keySet());
    double sigmaY = sigmaY(obsPred.values());
    double sigmaY2 = sigmaYSquare(obsPred.values());
    double sigmaXY = sigmaXY(obsPred);
    double numerator = (obsPred.size()*sigmaXY) - (sigmaX*sigmaY);
    double denominator = Math.sqrt(((obsPred.size()*sigmaX2)-Math.pow(sigmaX,2)))*Math.sqrt(((obsPred.size()*sigmaY2)-Math.pow(sigmaY,2)));
    return numerator/denominator;
}

TreeMap getRegressionPredictions(TreeMap pathObs){
    TreeMap rtn = new TreeMap();
    double sigmaX = sigmaX(pathObs.keySet());
    double sigmaX2 = sigmaXSquare(pathObs.keySet());
    double sigmaY = sigmaY(pathObs.values());
    double sigmaXY = sigmaXY(pathObs);
    double slope = getLeastSquareSlope(sigmaX,sigmaX2,sigmaY,sigmaXY,pathObs.size());//compute the slope with sign
    double constantC = getLeastSquareC(sigmaX,sigmaX2,sigmaY,sigmaXY,pathObs.size());
    for(Iterator i=pathObs.entrySet().iterator();i.hasNext();){
        Map.Entry e = (Map.Entry)i.next();
        Double key = (Double)e.getKey();
        double predictedVal = slope*key.doubleValue()+constantC;
        rtn.put(key,new Double(predictedVal));
    }
    return rtn;
}

double getCorrelation(){
    //to be implemented
    return 0;
}

static public double sigmaX(Set dateSet){
    double rtn = 0;
    int j = 0;
    Double first = new Double(0);
    for(Iterator i = dateSet.iterator();i.hasNext();){
        Double key = (Double)i.next();
        if(j==0)
            first = key;
        rtn = rtn + (key.doubleValue()-first.doubleValue());
        j++;
    }
    return rtn;
}

static public double sigmaXSquare(Set dateSet){
double rtn = 0;
int j = 0;
Double first = new Double(0);
for(Iterator i = dateSet.iterator();i.hasNext();){
    Double key = (Double)i.next();
    if(j==0)
        first = key;
    rtn = rtn + Math.pow((key.doubleValue()-first.doubleValue()),2);
    j++;
}
return rtn;
}



static public double sigmaY(Collection values){
double rtn = 0;
for(Iterator i = values.iterator();i.hasNext();){
    Double ctVal = (Double)i.next();
    rtn = rtn + ctVal.doubleValue();
}
return rtn;
}


static public double sigmaYSquare(Collection values){
double rtn = 0;
for(Iterator i = values.iterator();i.hasNext();){
    Double ctVal = (Double)i.next();
    rtn = rtn + Math.pow(ctVal.doubleValue(),2);
}
return rtn;
}

static public double sigmaXY(TreeMap series){
double rtn = 0;
Double first = (Double)series.firstKey();
for(Iterator i = series.entrySet().iterator();i.hasNext();){
    Map.Entry e = (Map.Entry) i.next();
    Double key = (Double)e.getKey();
    Double ctVal = (Double)e.getValue();
    rtn = rtn + ((key.doubleValue()-first.doubleValue())*ctVal.doubleValue());
}
return rtn;
}


public static double  getLeastSquareSlope(double sigX,double sigX2,double sigY,double sigXY, int N){
double num = ((N*sigXY) - (sigX*sigY));
double den = ((N*sigX2) - Math.pow(sigX,2));
return num/den;
}

public static double  getLeastSquareC(double sigX,double sigX2,double sigY,double sigXY,int N){
double num = ((sigX2*sigY) - (sigXY*sigX));
double den = ((N*sigX2) - Math.pow(sigX,2));
return num/den;
}
}
